1. Field of the Invention
This invention relates to Single-Hop Interconnection (SHI) multichannel networks in general and, more specifically, to a SHI network signal transmission procedure for composing larger SHI networks from a plurality of smaller Shared Directional Multichannels (SDMs) while maintaining or improving wiring efficiency and concurrency.
2. Description of the Related Art
The evolution of modern data communications networks has steadily increased the demand for networks offering high data transmission speeds and high levels of data parallelism or channel concurrency. Data transmission rates are limited by the physical technology composing the network interconnection linkages and by the station transmission and reception capacities. Channel concurrency is limited by the requirement that multiple message signal transmissions remain distinguishable within the network when routed to the appropriate destinations. With standard bus-oriented network architectures, the number of concurrent message signals is less than or equal to the number of buses.
The art is replete with bus-oriented SHI techniques for improving channel concurrency within a communication network. Such techniques are not limited to any particular physical communication technology. Recent improvements in fiber optic transmission technology and the invention of the optical star coupler have given rise to an explosive growth of optical network applications. The optical data transmission analogy is favored because of the very high data transmission rates possible at optical frequencies. Unfortunately, this optical bandwidth does little by itself to improve channel concurrency in switched networks. Without circuit components capable of optical switching speeds or wavelength-selective components capable of exploiting multiple optical channels, concurrency limitations continue to be an obtrusive handicap for optical data transmission networks.
Alternate proposals for overcoming these optical switching limitations suggest using non-bus-oriented SHI networks, including those employing the SDM, such as those discussed by Matthew T. Busche, et al, "On Optical Interconnection of Stations Having Multiple Transmitters and Receivers", 1990 International Symposium on Information Theory and its Applications (ISITA '90), Hawaii, U.S.A., Nov. 27-30, 1990, Session 63-3, pp. 967-970. See also Y. Birk, et al, "Bus-Oriented Interconnection Topologies for Single-Hop Communications Among Multi-Transceiver Stations", IEEE Infocon '88, pp. 558-567, IEEE Computer Society Press, 1988. For an early discussion of non-bus-oriented SHIs, see Y. Birk, "Concurrent Communication Among Multi-Transceiver Stations Over Shared Media", PhD Dissertation, Stanford University, December 1986.
A SDM consists of a set of inputs, a set of outputs, and a specification of the subset of outputs reachable from each input. A SDM is used to form a SHI by connecting a transmitter to each SDM input and a receiver to each SDM output. When a transmitter transmits a message, the message is heard by all receivers reachable from it. A message is received successfully by a receiver if and only if (a) that receiver is the intended recipient, (b) that receiver is reachable from the transmitter, and (c) that receiver hears no other "colliding" message signal at the same time.
It has been shown in theory how a SDM can be used to construct passive, static, SHIs between a set of Source Stations (SSs), each SS with one or more transmitter outputs, and a set of Destination Stations (DSs), each DS having one or more receiver inputs; such a SDM permits a large number of concurrent, non-interfering message signal transmissions if every SS has at least two outputs and every DS has at least two inputs (Y. Birk, et al, "On the Uniform-Traffic Capacity of Single-Hop Interconnections Employing Shared Directional Multichannels", IBM Research Report RJ7859, December, 1990, IBM Corp., Armonk, N.Y., referred to hereinafter as "Birk et al (1990)"). The terms "passive" and "static" as used herein denote that the SDM is fixed (no switches), and that there is a transmitter output in the SS and a receiver input in the DS for each (SS, DS) pair such that the latter can hear the message signal transmitted from the former without active components or repeater stations in the signal path.
The SHIs employing SDMs lend themselves to an implementation using optical fibers and directional star couplers. A directional star coupler is an element with several input fibers and several output fibers. An optical signal presented an any input is spread among all outputs but does not spread retrogressively to any of the other input fibers. The star coupler is unlike an optical switching coupler in that the optical signal at any input fiber is passively distributed equally among all output fibers.
In U.S. Pat. No. 4,708,424, Michel Marhic discloses a method for interconnecting smaller star couplers to synthesize large single-mode stars. Marhic teaches the use of 2-star fiber optic couplers having two inputs and two outputs as building blocks to form 2N-star couplers of any desired size and shows that the power spreading losses in such 2N-star couplers is substantially equal to the factor associated with the larger of either the number of inputs (in-degree) or the number of outputs (out-degree) of the star.
More precisely, when all fibers used in a star coupler are of equal cross-section, as is usually the case, the ratio of the signal power presented at an input to the power emerging from any output is equal to the maximum of the "in-degree" or the "out-degree" of the star coupler. Therefore, for a SHI of (m) SSs each having (a) transmitter outputs and (n) DSs each having (b) receiver inputs, implemented by connecting each transmitter to a (1 by n/a) coupler and each receiver to a (m/b by 1) coupler, with fibers between the two coupler types, a signal must travel through a (1 by n/a) coupler followed by a (m/b by 1) coupler when traversing the SDM between transmitter and receiver. The practical problem with this scheme is that the signal power at a receiver must then be the transmitted power divided by n.sup.2 /(ab), assuming m=n. This quadratic spreading loss limits the number of DSs and SSs that may be connected passively to no more than 15-20.
The notation known in the art for an SDM-based SHI such o as discussed above is (a,b;m,n) denoting (#outputs, #inputs; #SSs, #DSs). As used herein, an "efficient" SHI denotes an SHI with a spreading loss that is linear in n=m. Heuristically, any wiring of an SDM-based SHI must permit the message signal to be split (n/a) ways because each transmitter must reach (n/a) receivers. Similarly, (m/b) signals must be combined at each receiver because each receiver is connected to (m/b) transmitter outputs. Therefore, the minimal power split intuitively possible is max(n/a, m/b).
In the above-cited Birk patent, Birk teaches a system for selecting the number of and specifications for several coupling stages and a wiring method that permits the interconnection of (m) SSs each having two transmitter outputs, and (n) DSs each having one receiver input, such that the power spreading loss is no more than twice the intuitively optimal value, increasing linearly in (n) rather than quadratically. However, the above-cited Birk patent does not consider the problem of optimally connecting a set of SSs to a set of DSs where neither (a) nor (b) is unity.
In the Birk et al (1990) reference cited above, it is shown to be theoretically possible to construct a third SHI from a plurality of first and second SDMs such that the number of concurrent non-interfering signal transmissions in the third SHI is the product of the respective channel signal concurrencies in the two constituent SDMs. However, until now, there was no available practical method for constructing such a SHI in a manner that avoids quadratic growth in wiring, power spreading loss and complexity, without sacrificing this gain in message concurrency. Using the above notation, the third SHI is described as (a.sub.1 a.sub.2, b.sub.1 b.sub.2 ; m.sub.1 m.sub.2, n.sub.1 n.sub.2) in terms of the two constituents, (a.sub.1,b.sub.1 ;m.sub.1,n.sub.1) and (a.sub.2,b.sub.2 :m.sub.2,n.sub.2).
For instance, Birk et al (1990) show how to choose the connections and schedule message transmissions such that, for (n) SSs, each with (a) transmitters, and (n) DSs, each with (b) receivers, the SHI (a,b;n,n) can sustain roughly (log.sub.2 n).sup.a+b-2 concurrent non-interfering signal transmissions for a uniform traffic pattern. While the performance reward for increasing the number of transmitters and receivers is substantial, the natural manner of directly configuring the wiring according to the station connection list requires numbers of wires and directional couplers and (for fiber optic implementations) transmission power that grow quadratically (in proportion to n.sup.2) with increasing numbers of stations.
With fiber-optic implementations, this quadratic spreading loss problem requires either active repeaters or a severe restriction on the maximum number of stations to 15-20 at the most. This limitation results from the above-mentioned peculiar power-spreading properties of the fiber-optic star coupler, for which the ratio of input power to output power is equal to max (in-degree, out-degree) rather than the out-degree alone.
The above-cited Birk patent teaches how, for b=1, a canonical SDM form can be used as a non-bus-oriented SHI offering a concurrency of k=( log.sub.a n choose (a-1))=( log.sub.a n )!/(a-1)!/( log.sub.a n -a+1)! with a power spreading loss of (2n/a). Birk teaches a procedure for efficiently transmitting signals in a specific interconnection when a=2b=2 or b=2a=2. However, the more general theoretical teachings by Birk et al (1990) for composing any two given SDMs to form a larger one, until now, have not been implemented in a manner that avoids quadratic spreading losses.
There is a strongly felt need in the optical network art for such a high concurrency passive SHI suitable for efficient signal transmission with a power split loss that grows linearly instead of quadratically with (n) and a component count that is optimal under the constraint of optimal power budget. The above-cited Birk patent solves this problem for a=1 or b=1, but does not teach or suggest means for efficient signal transmission through a SHI of general size without encountering quadratic increases in spreading loss and component count. The associated problems and unresolved deficiencies are clearly felt in the art and are solved by this invention in the manner described below.